package com.ntd.study.algorithm.sort.impl;

import com.ntd.study.algorithm.sort.Sort;

import java.util.LinkedList;
import java.util.List;
import java.util.function.BiFunction;

/**
 * 插入排序
 *
 * @author liuwenju
 * @date 2021/4/16
 */
public class SortInsert<T> implements Sort<T> {
    @Override
    public T[] sort(T[] arrays, BiFunction<T, T, Boolean> sort) {
        List<T> integerList = new LinkedList<>();
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arrays.length; i++) {
            // 记录要插入的数据
            T tmp = arrays[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && !sort.apply(tmp, arrays[j - 1])) {
                arrays[j] = arrays[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arrays[j] = tmp;
            }
        }
        return arrays;
    }
}
